Ma trận kề

Trong Toán họcKhoa học máy tính, ma trận kề (tiếng Anh: adjacency matrix) cho một đồ thị hữu hạn G gồm n đỉnh là một ma trận n × n, trong đó, các ô không nằm trên đường chéo chính aij là số cạnh nối hai đỉnh i và j, còn ô nằm trên đường chéo chính aii là hai lần số khuyên tại đỉnh i, hoặc chỉ là số khuyên tại đỉnh đó (bài này chọn cách thứ nhất, các đồ thị có hướng luôn theo cách thứ hai). Mỗi đồ thị có duy nhất một ma trận kề, các đồ thị khác nhau có các ma trận kề khác nhau. Trong trường hợp đặc biệt của đồ thị đơn hữu hạn, ma trận kề là một ma trận (0,1) với các giá trị 0 nằm trên đường chéo chính. Nếu đồ thị là vô hướng, ma trận kề là ma trận đối xứng.Đối với đồ thị thưa, nghĩa là đồ thị có ít cạnh, người ta thường chọn dùng danh sách kề hơn do nó chiếm ít bộ nhớ hơn. Ma trận liên thuộc là một biểu diễn ma trận khác cho đồ thị.Quan hệ giữa một đồ thị và ma trận kề của nó được nghiên cứu trong lý thuyết phổ đồ thị (spectral graph theory)[1].